@Part[KSeque, Root = "CLM.MSS"]
@Comment{Chapter of Common Lisp Manual.  Copyright 1984 Guy L. Steele Jr.⎇

@MyChapter[Sequences]
@Label[KSEQUE]

The type @f[sequence] encompasses both lists and vectors (one-dimensional
arrays).
While these are different data structures with different structural
properties leading to different algorithmic uses, they do have a common
property: each contains an ordered set of elements.
Note that @nil is considered to be a sequence, of length zero.

There are some operations that are useful on both lists and arrays
because they deal with ordered sets of elements.  One may ask the number
of elements, reverse the ordering, extract a subsequence, and so on.  For
such purposes @clisp provides a set of generic functions on sequences:
@Lisp
@tabdivide[5]
elt@\reverse@\map@\remove
length@\nreverse@\some@\remove-duplicates
subseq@\concatenate@\every@\delete
copy-seq@\position@\notany@\delete-duplicates
fill@\find@\notevery@\substitute
replace@\sort@\reduce@\nsubstitute
count@\merge@\search@\mismatch
@Endlisp
Some of these operations come in more than one version.
Such versions are indicated by adding a suffix (or, occasionally, a prefix)
to the basic name of the operation.
In addition, many operations accept one or more optional keyword
arguments that can modify the operation in various ways.

If the operation requires testing sequence elements according to
some criterion, then the criterion may be specified in one of two ways.
The basic operation accepts an item,
and elements are tested for being @f[eql] to that item.
(A test other than @f[eql] can be specified by the @Kwd[test]
or @Kwd[test-not] keyword.  It is an error to use both
of these keywords in the same call.)
The variants formed by adding @f[-if] and @f[-if-not]
to the basic operation name do not take an item,
but instead a one-argument predicate,
and elements are tested for satisfying or not satisfying the predicate.
As an example,
@Lisp
(remove @i[item] @i[sequence])
@Endlisp
returns a copy of @i[sequence] from which all elements @f[eql] to @i[item]
have been removed;
@Lisp
(remove @i[item] @i[sequence] @Kwd[test] #'equal)
@Endlisp
returns a copy of @i[sequence] from which all elements @f[equal] to @i[item]
have been removed;
@Lisp
(remove-if #'numberp @i[sequence])
@Endlisp
returns a copy of @i[sequence] from which all numbers have been removed.

If an operation tests elements of a sequence in any manner,
the keyword argument @Kwd[key], if not @false, should be a function
of one argument that will extract from an element the part to be tested
in place of the whole element.
For example, the effect of the @maclisp expression
@f[(assq item seq)] could be obtained by
@Lisp
(find @i[item] @i[sequence] @Kwd[test] #'eq @Kwd[key] #'car)
@Endlisp
This searches for the first element of @i[sequence] whose @i[car] is @f[eq]
to @i[item].

For some operations it can be useful to specify the direction
in which the sequence is conceptually processed.  In this case the basic
operation normally processes the sequence in the forward direction,
and processing in the reverse direction is indicated by a non-@false
value for the keyword argument @Kwd[from-end].  (The processing order
specified by the @Kwd[from-end] is purely conceptual.  Depending on
the object to be processed and on the implementation, the actual processing
order may be different.  For this reason a user-supplied @i[test] function
should be free of side effects.)

Many operations allow the specification of a subsequence to be operated
upon.  Such operations have keyword arguments
called @Kwd[start] and @Kwd[end].  These arguments should be integer indices
into the sequence, with @i[start]@Sail[≤]@i[end]
(it is an error if @i[start]@sail[>]@i[end]).  They indicate
the subsequence starting with and @i[including] element @i[start]
and up to but @i[excluding] element @i[end].  The length of the subsequence
is therefore @i[end]@Minussign@;@i[start].  If @i[start] is omitted,
it defaults to zero; and if @i[end] is omitted or @false, it defaults to
the length of the sequence.
Therefore if both @i[start] and @i[end] are omitted the entire sequence
is processed by default.
For the most part, subsequence specification
is permitted purely for the sake of efficiency;
one can simply call @f[subseq] instead to extract the subsequence
before operating on it.  Note, however, that operations that
calculate indices
return indices into the original sequence, not into the subsequence:
@Lisp
(position #\b "foobar" @Kwd[start] 2 @Kwd[end] 5) @EV 3
(position #\b (subseq "foobar" 2 5)) @EV 1
@Endlisp
If two sequences are involved, then
the keyword arguments
@Kwd[start1], @Kwd[end1], @Kwd[start2], and @Kwd[end2] are used to
specify separate subsequences for each sequence.

For some functions, notably @f[remove] and @f[delete], the keyword argument
@Kwd[count] is used to specify how many occurrences of the item should
be affected.  If this is @false or is not supplied, all matching items are
affected.

In the following function descriptions, an element @i[x] of a sequence
``satisfies the test'' if any of the following holds:
@Begin[Itemize]
A basic function was called,
@i[testfn] was specified by the keyword @Kwd[test], and
@f[(funcall @i[testfn] @i[item] (@i[keyfn] @i[x]))] is true.

A basic function was called,
@i[testfn] was specified by the keyword @Kwd[test-not], and
@f[(funcall @i[testfn] @i[item] (@i[keyfn] @i[x]))] is false.

An @f[-if] function was called, and
@f[(funcall @i[predicate] (@i[keyfn] @i[x]))] is true.

An @f[-if-not] function was called, and
@f[(funcall @i[predicate] (@i[keyfn] @i[x]))] is false.
@End[Itemize]
In each case @i[keyfn] is the
value of the @Kwd[key] keyword argument (the default being the identity
function).  See, for example, @Funref[remove].

In the following function descriptions,
two elements @i[x] and @i[y] taken from sequences ``match'' if
either of the following holds:
@Begin[Itemize]
@i[testfn] was specified by the keyword @Kwd[test], and
@f[(funcall @i[testfn] (@i[keyfn] @i[x]) (@i[keyfn] @i[y]))] is true.

@i[testfn] was specified by the keyword @Kwd[test-not], and
@f[(funcall @i[testfn] (@i[keyfn] @i[x]) (@i[keyfn] @i[y]))] is false.
@End[Itemize]
See, for example, @Funref[search].

You may depend on the order in which arguments
are given to @i[testfn]; this permits the use of non-commutative
test functions in a predictable manner.
The order of the arguments to @i[testfn] corresponds
to the order in which those arguments (or the sequences containing
those arguments)
were given to the sequence function in question.
If a sequence function gives two elements from the same
sequence argument to @i[testfn], they are given in the same order in
which they appear in the sequence.

Whenever a sequence function must construct and return
a new vector, it always returns a @i[simple]
vector (see section @ref[ARRAY-TYPE-SECTION]).
Similarly, any strings constructed will be simple strings.

@Section[Simple Sequence Functions]

Most of the following functions perform simple operations on a single
sequence; @f[make-sequence] constructs a new sequence.

@Defun[Fun {elt⎇, Args {@i[sequence] @i[index]⎇]
This returns the element of @i[sequence] specified by @i[index],
which must be a non-negative integer less than the length of the @i[sequence]
as returned by @Funref[length].
The first element of a sequence has index @f[0].

(Note that @f[elt] observes the fill pointer in those vectors that have
fill pointers.  The array-specific function @Funref[aref] may be used
to access vector elements that are beyond the vector's fill pointer.)

@Macref[setf] may be used with @f[elt] to destructively replace
a sequence element with a new value.
@Enddefun

@Defun[Fun {subseq⎇, Args {@i[sequence] @i[start] @optional @i[end]⎇]
This returns the subsequence of @i[sequence] specified by @i[start] and
@i[end].
@f[subseq] @i[always] allocates a new sequence for a result; it never
shares storage with an old sequence.  The result subsequence is always of
the same type as the argument @i[sequence].

@Macref[setf] may be used with @f[subseq] to destructively replace
a subsequence with a sequence of new values; see also @Funref[replace].
@Enddefun

@Defun[Fun {copy-seq⎇, Args {@i[sequence]⎇]
A copy is made of the argument @i[sequence]; the result is @f[equalp]
to the argument but not @f[eq] to it.
@Lisp
(copy-seq @i[x]) @EQ (subseq @i[x] 0)
@Endlisp
but the name @f[copy-seq] is more perspicuous when applicable.
@Enddefun

@Defun[Fun {length⎇, Args {@i[sequence]⎇]
The number of elements in @i[sequence] is returned as a non-negative integer.
If the sequence is a vector with a fill pointer,
the ``active length'' as specified by the fill pointer is returned.
See section @ref[FILL-POINTER].
@Enddefun

@Defun[Fun {reverse⎇, Args {@i[sequence]⎇]
The result is a new sequence of the same kind as @i[sequence],
containing the same elements but in reverse order.
The argument is not modified.
@Enddefun

@Defun[Fun {nreverse⎇, Args {@i[sequence]⎇]
The result is a sequence containing the same elements as @i[sequence]
but in reverse order.  The argument may be destroyed and re-used to
produce the result.  The result may or may not be @f[eq] to the
argument, so it is usually wise to say something like
@f[(setq x (nreverse x))], because simply @f[(nreverse x)] is not
guaranteed to leave a reversed value in @f[x].
@Enddefun

@Defun[Fun {make-sequence⎇, Args {@i[type] @i[size]⎇, Keys {[initial-element]⎇]
This returns a sequence of type @i[type] and of length @i[size], each of
whose elements
has been initialized to the @Kwd[initial-element] argument.
If specified, the @Kwd[initial-element] argument must be an object that
can be an element of a sequence of type @i[type].
For example:
@lisp
(make-sequence '(vector double-float) 100
	       :initial-element 1d0)
@Endlisp
If an @Kwd[initial-element] argument is not specified, then the sequence will
be initialized in an implementation-dependent way.
@Enddefun

@Section[Concatenating, Mapping, and Reducing Sequences]

The functions in this section each operate on an arbitrary number of
sequence except for @f[reduce], which is included here because
of its conceptual relationship to the mapping functions.

@Defun[Fun {concatenate⎇, Args {@i[result-type] @rest @i[sequences]⎇]
The result is a new sequence that contains all the elements of all the
sequences in order.  All of the sequences are copied from; the result
does not share any structure with any of the argument sequences (in this
@f[concatenate] differs from @f[append]).  The type of the result is
specified by @i[result-type], which must be a subtype of @f[sequence],
as for the function @Funref[coerce].
It must be possible for every element of the argument sequences to be an
element of a sequence of type @i[result-type].

If only one @i[sequence] argument is provided
and it has the type specified by @i[result-type],
@f[concatenate] is required to copy the argument rather than simply
returning it.  If a copy is not required, but only possible type-conversion,
then the @Funref[coerce] function may be appropriate.
@Enddefun

@Defun[Fun {map⎇, Args {@i[result-type] @i[function] @i[sequence] @rest @i[more-sequences]⎇]
The @i[function] must take as many arguments as there are sequences
provided; at least one sequence must be provided.
The result of @f[map] is a sequence such that element @i[j] is the result
of applying @i[function] to element @i[j] of each of the argument
sequences.  The result sequence is as long as the shortest of the
input sequences.

If the @i[function] has side effects, it can count on being called
first on all the elements numbered @f[0], then on all those
numbered @f[1], and so on.

The type of the result sequence is specified by the argument @i[result-type]
(which must be a subtype of the type @f[sequence]),
as for the function @Funref[coerce].
In addition, one may specify @nil for the result type, meaning that no
result sequence is to be produced; in this case the @i[function] is invoked
only for effect, and @f[map] returns @nil.  This gives an effect similar
to that of @Funref[mapc].

@Incompatibility{In @maclisp, @lmlisp, @interlisp, and indeed even
@lisp15, the function @f[map] has always meant a non-value-returning
version.  However, standard computer science literature, including,
in particular,
the recent wave of papers on ``functional programming,'' have come
to use @f[map] to mean
what in the past @xlisp implementations have called @f[mapcar].
To simplify things henceforth, @clisp follows current usage,
and what was formerly called @f[map] is named @Funref[mapl] in @clisp.⎇
For example:
@lisp
(map 'list #'- '(1 2 3 4)) @EV (-1 -2 -3 -4)
(map 'string
     #'(lambda (x) (if (oddp x) #\1 #\0))
     '(1 2 3 4))
   @EV "1010"
@Endlisp
@Enddefun

@Defun[Fun {some⎇, Args {@i[predicate] @i[sequence] @rest @i[more-sequences]⎇]
@Defun1[Fun {every⎇, Args {@i[predicate] @i[sequence] @rest @i[more-sequences]⎇]
@Defun1[Fun {notany⎇, Args {@i[predicate] @i[sequence] @rest @i[more-sequences]⎇]
@Defun1[Fun {notevery⎇, Args {@i[predicate] @i[sequence] @rest @i[more-sequences]⎇]
These are all predicates.
The @i[predicate] must take as many arguments as there are sequences
provided.  The @i[predicate] is first applied to the elements
with index @f[0] in each of the sequences, and possibly then to
the elements with index @f[1], and so on, until a termination
criterion is met or the end of the shortest of the @i[sequences] is reached.

If the @i[predicate] has side effects, it can count on being called
first on all the elements numbered @f[0], then on all those
numbered @f[1], and so on.

@f[some] returns as soon as any invocation of @i[predicate]
returns a non-@false value; @f[some] returns that value.
If the end of a sequence is reached, @f[some] returns @false.
Thus, considered as a predicate, it is true if @i[some] invocation of
@i[predicate] is true.

@f[every] returns @false as soon as any invocation of @i[predicate]
returns @false.
If the end of a sequence is reached, @f[every] returns a non-@false value.
Thus, considered as a predicate, it is true if @i[every] invocation of
@i[predicate] is true.

@f[notany] returns @false as soon as any invocation of @i[predicate]
returns a non-@false value.
If the end of a sequence is reached, @f[notany] returns a non-@false value.
Thus, considered as a predicate, it is true if @i[no] invocation of
@i[predicate] is true.

@f[notevery] returns a non-@false value as soon as any invocation
of @i[predicate] returns @false.  If the end of a sequence is reached,
@f[notevery] returns
@false.  Thus, considered as a predicate, it is true if @i[not every] invocation of
@i[predicate] is true.

@Incompatibility{The order of the arguments here is not compatible
with @interlisp and @lmlisp.  This is to stress the similarity
of these functions to @f[map].  The functions are therefore extended
here to functions of more than one argument, and to multiple sequences.⎇
@Enddefun


@Defun[Fun {reduce⎇, Args {@i[function] @i[sequence]⎇, Keys{[from-end][start][end][initial-value]⎇]
The @f[reduce] function combines all the elements of a sequence using
a binary operation; for example, using @f[+] one can add up all the
elements.

The specified subsequence of the @i[sequence] is combined
or ``reduced'' using the
@i[function], which must accept two arguments.  The reduction is
left-associative, unless the @Kwd[from-end] argument is true (it defaults
to @nil), in which case it is right-associative.  If an
@Kwd[initial-value] argument is given, it is logically placed before the
subsequence (after it if @Kwd[from-end] is true) and included in the
reduction operation.

If the specified subsequence contains exactly one element
and no @Kwd[initial-value]
is given, then that element
is returned and the @i[function] is not called.
If the specified subsequence is empty and an @Kwd[initial-value] is given,
then the @Kwd[initial-value] is returned
and the @i[function] is not called.

If the specified subsequence is empty and no @Kwd[initial-value] is given,
then the @i[function] is called with zero
arguments, and @f[reduce] returns whatever the function does.  (This is
the only case where the @i[function] is called with other than two
arguments.)

@lisp
(reduce #'+ '(1 2 3 4)) @ev 10
(reduce #'- '(1 2 3 4)) @eq (- (- (- 1 2) 3) 4) @ev -8
(reduce #'- '(1 2 3 4) :from-end t)	;@r[Alternating sum.]
   @eq (- 1 (- 2 (- 3 4))) @ev -2
(reduce #'+ '()) @ev 0
(reduce #'+ '(3)) @ev 3
(reduce #'+ '(foo)) @ev foo
(reduce #'list '(1 2 3 4)) @ev (((1 2) 3) 4)
(reduce #'list '(1 2 3 4) :from-end t) @ev (1 (2 (3 4)))
(reduce #'list '(1 2 3 4) :initial-value 'foo)
   @ev ((((foo 1) 2) 3) 4)
(reduce #'list '(1 2 3 4)
	:from-end t :initial-value 'foo)
   @ev (1 (2 (3 (4 foo))))
@Endlisp
If the @i[function] produces side effects, the order of the calls
to the @i[function] can be correctly predicted from the reduction ordering
demonstrated above.

The name ``reduce'' for this function is borrowed from @apl.
@Enddefun

@Section[Modifying Sequences]

Each of these functions alters the contents of a sequence or produces
an altered copy of a given sequence.

@Defun[Fun {fill⎇, Args {@i[sequence] @i[item]⎇, Keys {[start][end]⎇]
The @i[sequence] is destructively modified by replacing each element of
the subsequence specified by the @Kwd[start] and @Kwd[end] parameters
with the @i[item].  The @i[item] may be any @xlisp object but must be a
suitable element for the @i[sequence].  The @i[item] is stored into all
specified components of the @i[sequence], beginning at the one specified
by the @Kwd[start] index (which defaults to zero), up to but not
including the one specified by the @Kwd[end] index (which defaults to the
length of the sequence).  @f[fill] returns the modified @i[sequence].
For example:
@lisp
(setq x (vector 'a 'b 'c 'd 'e)) @EV #(a b c d e)
(fill x 'z @Kwd[start] 1 @Kwd[end] 3) @EV #(a z z d e)
  @r[and now] x @EV #(a z z d e)
(fill x 'p) @EV #(p p p p p)
  @r[and now] x @EV #(p p p p p)
@Endlisp
@Enddefun

@Defun[Fun {replace⎇, Args {@i[sequence1] @i[sequence2]⎇, Keys {[start1][end1][start2][end2]⎇]
The sequence @i[sequence1] is destructively modified by copying successive
elements into it from @i[sequence2].  The elements of
@i[sequence2] must be of a type that may be stored into
@i[sequence1].  The subsequence of @i[sequence2]
specified by @Kwd[start2] and @Kwd[end2] is copied into the
subsequence of @i[sequence1] specified by @Kwd[start1] and @Kwd[end1].
(The arguments @Kwd[start1] and @Kwd[start2] default to zero.
The arguments @Kwd[end1] and @Kwd[end2] default
to @false, meaning the end of the appropriate sequence.)
If these subsequences are not of the same length, then
the shorter length determines how many elements are copied; the extra
elements near the end of the longer subsequence are not involved in the
operation.
The number of elements copied may be expressed as:
@Lisp
(min (- @i[end1] @i[start1]) (- @i[end2] @i[start2]))
@Endlisp
The value returned by @f[replace] is the modified @i[sequence1].

If @i[sequence1] and @i[sequence2] are the same (@f[eq]) object
and the region being modified overlaps the region being copied
from, then it is as if the entire source region were copied to another
place and only then copied back into the target region.
However, if @i[sequence1] and @i[sequence2] are @i[not] the same,
but the region being modified overlaps the region being copied from
(perhaps because of shared list structure or displaced arrays),
then after the @f[replace] operation
the subsequence of @i[sequence1] being modified will have
unpredictable contents.
@Enddefun

@Defun[Fun {remove⎇, Args {@i[item] @i[sequence]⎇, Keys {[from-end][test][test-not][start][end]⎇, MoreKeys = {[count][key]⎇]
@Defun1[Fun {remove-if⎇, Args {@i[test] @i[sequence]⎇, Keys {[from-end][start][end][count][key]⎇]
@Defun1[Fun {remove-if-not⎇, Args {@i[test] @i[sequence]⎇, Keys {[from-end][start][end][count][key]⎇]
The result is a sequence of the same kind as the argument @i[sequence]
that has the same elements except that those in the subsequence
delimited by @Kwd[start] and @Kwd[end] and satisfying the test (see
above) have been removed.  This is a non-destructive operation; the result
is a copy of the input @i[sequence], save that some elements are not
copied.  Elements not removed occur in the same order in the result
that they did in the argument.

The @Kwd[count] argument, if supplied, limits the number of elements
removed; if more than @Kwd[count] elements satisfy the test,
then of these elements only the leftmost are removed,
as many as specified by @kwd[count].

A non-@false @Kwd[from-end] specification
matters only when the @Kwd[count] argument
is provided; in that case only the rightmost @Kwd[count] elements satisfying
the test are removed.
For example:
@lisp
(remove 4 '(1 2 4 1 3 4 5)) @EV (1 2 1 3 5)
(remove 4 '(1 2 4 1 3 4 5) @Kwd[count] 1) @EV (1 2 1 3 4 5)
(remove 4 '(1 2 4 1 3 4 5) @Kwd[count] 1 @Kwd[from-end] t)
   @EV (1 2 4 1 3 5)
(remove 3 '(1 2 4 1 3 4 5) @Kwd[test] #'>) @EV (4 3 4 5)
(remove-if #'oddp '(1 2 4 1 3 4 5)) @EV (2 4 4)
(remove-if #'evenp '(1 2 4 1 3 4 5) @Kwd[count] 1 @Kwd[from-end] t)
   @EV (1 2 4 1 3 5)
@Endlisp
The result of @f[remove] may share
with the argument @i[sequence]; a list result may share a tail
with an input list, and the result may be @f[eq] to the input @i[sequence]
if no elements need to be removed.
@Enddefun

@Defun[Fun {delete⎇, Args {@i[item] @i[sequence]⎇, Keys {[from-end][test][test-not][start][end]⎇, MoreKeys = {[count][key]⎇]
@Defun1[Fun {delete-if⎇, Args {@i[test] @i[sequence]⎇, Keys {[from-end][start][end][count][key]⎇]
@Defun1[Fun {delete-if-not⎇, Args {@i[test] @i[sequence]⎇, Keys {[from-end][start][end][count][key]⎇]
This is the destructive counterpart to @f[remove].
The result is a sequence of the same kind as the argument @i[sequence]
that has the same elements except that those in the subsequence
delimited by @Kwd[start] and @Kwd[end] and satisfying the test (see
above) have been deleted.  This is a destructive operation.
The argument @i[sequence] may be destroyed and used to construct
the result; however, the result may or may not be @f[eq] to @i[sequence].
Elements not deleted occur in the same order in the result
that they did in the argument.

The @Kwd[count] argument, if supplied, limits the number of elements
deleted; if more than @Kwd[count] elements satisfy the test,
then of these elements only the leftmost are deleted,
as many as specified by @kwd[count].

A non-@false @Kwd[from-end] specification
matters only when the @Kwd[count] argument
is provided; in that case only the rightmost @Kwd[count] elements satisfying
the test are deleted.
For example:
@lisp
(delete 4 '(1 2 4 1 3 4 5)) @EV (1 2 1 3 5)
(delete 4 '(1 2 4 1 3 4 5) @Kwd[count] 1) @EV (1 2 1 3 4 5)
(delete 4 '(1 2 4 1 3 4 5) @Kwd[count] 1 @Kwd[from-end] t)
   @EV (1 2 4 1 3 5)
(delete 3 '(1 2 4 1 3 4 5) @Kwd[test] #'>) @EV (4 3 4 5)
(delete-if #'oddp '(1 2 4 1 3 4 5)) @EV (2 4 4)
(delete-if #'evenp '(1 2 4 1 3 4 5) @Kwd[count] 1 @Kwd[from-end] t)
   @EV (1 2 4 1 3 5)
@Endlisp
@Incompatibility{In @maclisp, the @f[delete] function uses
an @f[equal] comparison rather than @f[eql], which is the default
test for @f[delete] in @clisp.  Where in @maclisp one would write
@f[(delete x y)], one must in @clisp write @f[(delete x y :test #'equal)]
to get the completely identical effect.  Similarly, one can get the
precise effect, and no more, of the @maclisp @f[(delq x y)]
by writing in @clisp @f[(delete x y :test #'eq)].⎇
@Enddefun

@Defun[Fun {remove-duplicates⎇, Args {@i[sequence]⎇, Keys {[from-end][test][test-not]⎇, Morekeys {[start][end][key]⎇]
@Defun1[Fun {delete-duplicates⎇, Args {@i[sequence]⎇, Keys {[from-end][test][test-not]⎇, Morekeys {[start][end][key]⎇]
The elements of @i[sequence] are compared pairwise, and if any two match,
then the one occurring earlier in the sequence
is discarded (but if the @Kwd[from-end] argument is true, then the one
later in the sequence is discarded).
The result is a sequence of the same kind as the
argument sequence with enough elements removed so that no two of the remaining
elements match.  The order of the elements remaining in the result
is the same as the order in which they appear in @i[sequence].

@f[remove-duplicates] is the non-destructive version
of this operation.
The result of @f[remove-duplicates] may share
with the argument @i[sequence]; a list result may share a tail
with an input list, and the result may be @f[eq] to the input @i[sequence]
if no elements need to be removed.

@f[delete-duplicates] may destroy the argument @i[sequence].

Some examples:
@Lisp
(remove-duplicates '(a b c b d d e)) @EV (a c b d e)
(remove-duplicates '(a b c b d d e) @Kwd[from-end] t) @EV (a b c d e)
(remove-duplicates '((foo #\a) (bar #\%) (baz #\A))
		   @Kwd[test] #'char-equal @Kwd[key] #'cadr)
   @EV ((bar #\%) (baz #\A))
(remove-duplicates '((foo #\a) (bar #\%) (baz #\A))
		   @Kwd[test] #'char-equal @Kwd[key] #'cadr @Kwd[from-end] t)
   @EV ((foo #\a) (bar #\%))
@Endlisp

These functions are useful for converting a sequence into a canonical
form suitable for representing a set.
@Enddefun

@Defun[Fun {substitute⎇, Args {@i[newitem] @i[olditem] @i[sequence]⎇, Keys {[from-end][test][test-not]⎇, Morekeys = {[start][end][count][key]⎇]
@Defun1[Fun {substitute-if⎇, Args {@i[newitem] @i[test] @i[sequence]⎇, Keys {[from-end][start][end]⎇, Morekeys = {[count][key]⎇]
@Defun1[Fun {substitute-if-not⎇, Args {@i[newitem] @i[test] @i[sequence]⎇, Keys {[from-end][start][end]⎇, Morekeys = {[count][key]⎇]
The result is a sequence of the same kind as the argument @i[sequence]
that has the same elements except that those in the subsequence
delimited by @Kwd[start] and @Kwd[end] and satisfying the test (see
above) have been replaced by @i[newitem].  This is a non-destructive
operation; the result is a copy of the input @i[sequence], save that some
elements are changed.

The @Kwd[count] argument, if supplied, limits the number of elements
altered; if more than @Kwd[count] elements satisfy the test,
then of these elements only the leftmost are replaced,
as many as specified by @kwd[count].


A non-@false @Kwd[from-end] specification
matters only when the @Kwd[count] argument
is provided; in that case only the rightmost @Kwd[count] elements satisfying
the test are removed.
For example:
@lisp
(substitute 9 4 '(1 2 4 1 3 4 5)) @EV (1 2 9 1 3 9 5)
(substitute 9 4 '(1 2 4 1 3 4 5) @Kwd[count] 1) @EV (1 2 9 1 3 4 5)
(substitute 9 4 '(1 2 4 1 3 4 5) @Kwd[count] 1 @Kwd[from-end] t)
   @EV (1 2 4 1 3 9 5)
(substitute 9 3 '(1 2 4 1 3 4 5) @Kwd[test] #'>) @EV (9 9 4 9 3 4 5)
(substitute-if 9 #'oddp '(1 2 4 1 3 4 5)) @EV (9 2 4 9 9 4 9)
(substitute-if 9 #'evenp '(1 2 4 1 3 4 5) @Kwd[count] 1 @Kwd[from-end] t)
   @EV (1 2 4 1 3 9 5)
@Endlisp
The result of @f[substitute] may share
with the argument @i[sequence]; a list result may share a tail
with an input list, and the result may be @f[eq] to the input @i[sequence]
if no elements need to be changed.

See also @Funref[subst], which performs substitutions throughout a tree.
@Enddefun

@Defun[Fun {nsubstitute⎇, Args {@i[newitem] @i[olditem] @i[sequence]⎇, Keys {[from-end][test][test-not]⎇, Morekeys = {[start][end][count][key]⎇]
@Defun1[Fun {nsubstitute-if⎇, Args {@i[newitem] @i[test] @i[sequence]⎇, Keys {[from-end][start][end]⎇, Morekeys = {[count][key]⎇]
@Defun1[Fun {nsubstitute-if-not⎇, Args {@i[newitem] @i[test] @i[sequence]⎇, Keys {[from-end][start][end]⎇, Morekeys = {[count][key]⎇]
This is the destructive counterpart to @f[substitute].
The result is a sequence of the same kind as the argument @i[sequence]
that has the same elements except that those in the subsequence
delimited by @Kwd[start] and @Kwd[end] and satisfying the test (see
above) have been replaced by @i[newitem].  This is a destructive operation.
The argument @i[sequence] may be destroyed and used to construct
the result; however, the result may or may not be @f[eq] to @i[sequence].

See also @Funref[nsubst], which performs destructive
substitutions throughout a tree.
@Enddefun

@section[Searching Sequences for Items]

Each of these functions searches a sequence to locate one or more
elements satisfying some test.

@Defun[Fun {find⎇, Args {@i[item] @i[sequence]⎇, Keys {[from-end][test][test-not][start][end][key]⎇]
@Defun1[Fun {find-if⎇, Args {@i[test] @i[sequence]⎇, Keys {[from-end][start][end][key]⎇]
@Defun1[Fun {find-if-not⎇, Args {@i[test] @i[sequence]⎇, Keys {[from-end][start][end][key]⎇]
If the @i[sequence] contains an element satisfying the test,
then the leftmost such element
is returned; otherwise @false is returned.

If @Kwd[start] and @Kwd[end] keyword arguments are given,
only the specified subsequence of @i[sequence] is searched.

If a non-@false @Kwd[from-end] keyword argument is specified, then the result is
the @i[rightmost] element satisfying the test.
@Enddefun

@Defun[Fun {position⎇, Args {@i[item] @i[sequence]⎇, Keys {[from-end][test][test-not][start][end][key]⎇]
@Defun1[Fun {position-if⎇, Args {@i[test] @i[sequence]⎇, Keys {[from-end][start][end][key]⎇]
@Defun1[Fun {position-if-not⎇, Args {@i[test] @i[sequence]⎇, Keys {[from-end][start][end][key]⎇]
If the @i[sequence] contains an element satisfying the test,
then the index within the sequence of the leftmost such element
is returned as a non-negative integer; otherwise @false is returned.

If @Kwd[start] and @Kwd[end] keyword arguments are given,
only the specified subsequence of @i[sequence] is searched.
However, the index returned is relative to the entire sequence,
not to the subsequence.

If a non-@false @Kwd[from-end] keyword argument is specified, then the result is
the index of the @i[rightmost] element satisfying the test.  (The index
returned, however, is an index from the left-hand end, as usual.)
@Enddefun

@Defun[Fun {count⎇, Args {@i[item] @i[sequence]⎇, Keys {[from-end][test][test-not][start][end][key]⎇]
@Defun1[Fun {count-if⎇, Args {@i[test] @i[sequence]⎇, Keys {[from-end][start][end][key]⎇]
@Defun1[Fun {count-if-not⎇, Args {@i[test] @i[sequence]⎇, Keys {[from-end][start][end][key]⎇]
The result is always a non-negative integer, the number of
elements in the specified subsequence of @i[sequence] satisfying
the test.

The @Kwd[from-end] argument does not affect the result returned;
it is accepted purely for compatibility with other sequence functions.
@Enddefun

@Defun[Fun {mismatch⎇, Args {@i[sequence1] @i[sequence2]⎇, Keys {[from-end][test][test-not][key]⎇, MoreKeys = {[start1][start2][end1][end2]⎇]
The specified subsequences of
@i[sequence1] and @i[sequence2] are compared element-wise.
If they are of equal length and match in every element, the result is
@false.  Otherwise, the result is a non-negative integer.
This result is the index within
@i[sequence1] of the leftmost position at which the two
subsequences fail to match; or,
if one subsequence is shorter than and a matching prefix of the other,
the result is the index
relative to @i[sequence1] beyond the last position tested.

If a non-@false @Kwd[from-end] keyword argument is given, then
@i[one plus] the index of the @i[rightmost]
position in which the sequences differ is returned.  In effect, the (sub)sequences
are aligned at their right-hand ends; then, the last elements are compared,
the penultimate elements, and so on.  The index returned is again
an index relative to @i[sequence1].
@Enddefun

@Defun[Fun {search⎇, Args {@i[sequence1] @i[sequence2]⎇, Keys {[from-end][test][test-not][key]⎇, MoreKeys = {[start1][start2][end1][end2]⎇]
A search is conducted for a subsequence of @i[sequence2] that
element-wise matches @i[sequence1].
If there is no such subsequence, the result is @false; if there is,
the result is the index into @i[sequence2] of the leftmost element
of the leftmost such matching subsequence.

If a non-@false @Kwd[from-end] keyword argument is given,
the index of the leftmost
element of the @i[rightmost] matching subsequence is returned.

The implementation may choose to search the sequence in any order;
there is no guarantee on the number of times the test is made.
For example, @f[search] with a non-@nil @Kwd[from-end]
argument might actually search a list from left to right
instead of from right to left (but in either case would return
the rightmost matching subsequence, of course).  Therefore it is a good
idea for a user-supplied predicate to be free of side effects.
@Enddefun

@Section[Sorting and Merging]

These functions may destructively modify argument sequences
in order to put a sequence into sorted order or to merge two
already sorted sequences.

@Defun[Fun {sort⎇, Args {@i[sequence] @i[predicate]⎇, Keys {[key]⎇]
@Defun1[Fun {stable-sort⎇, Args {@i[sequence] @i[predicate]⎇, Keys {[key]⎇]
@Index[sorting]
The @i[sequence] is destructively sorted according to an order determined by
the @i[predicate].  The @i[predicate] should take two
arguments, and return non-@false if and only if the first argument is
strictly less than the second (in some appropriate sense). 
If the first argument is greater than or equal to the second
(in the appropriate sense), then the @i[predicate] should return @false.

The @f[sort] function determines the relationship between two elements
by giving keys extracted from the elements to the @i[predicate].
The @Kwd[key] argument, when applied to an element, should return
the key for that element.  The @Kwd[key] argument defaults to the identity
function, thereby making the element itself be the key.

The @kwd[key] function should not have any side effects.
A useful example of a @kwd[key] function would be a component
selector function for a @Macref[defstruct] structure, used to sorting
a sequence of structures.
@Lisp
(sort @i[a] @i[p] @Kwd[key] @i[s])
   @EQ (sort @i[a] #'(lambda (x y) (@i[p] (@i[s] x) (@i[s] y))))
@Endlisp
While the above two expressions are equivalent, the first may be more
efficient in some implementations for certain types of arguments.  For
example, an implementation may choose to apply @i[s] to each
item just once, putting the resulting keys into a separate table, and
then sort the parallel tables, as opposed to applying
@i[s] to an item every time just before applying the @i[predicate].

If the @Kwd[key] and @i[predicate] functions always return, then the
sorting operation will always terminate, producing a sequence containing
the same elements as the original sequence (that is, the result is a
permutation of @i[sequence]).  This is guaranteed even if the
@i[predicate] does not really consistently represent a total order
(in which case the elements will be scrambled in some unpredictable
way, but no element will be lost).  If
the @Kwd[key] function consistently returns meaningful keys,
and the @i[predicate]
does reflect some total ordering criterion on those keys, then the
elements of the result sequence will be properly sorted according
to that ordering.

The sorting operation performed by @f[sort] is not guaranteed @i[stable].
Elements considered equal by the @i[predicate] may or may not
stay in their original order.  (The @i[predicate] is assumed to
consider two elements @i[x] and @i[y] to be equal if
@f[(funcall @i[predicate] @i[x] @i[y])] and
@f[(funcall @i[predicate] @i[y] @i[x])] are both false.)
The function @f[stable-sort] guarantees
stability, but may be slower than @f[sort] in some situations.

The sorting operation may be destructive in all cases.  In the case of an
array argument, this is accomplished by permuting the elements in place.
In the case of a list, the list is
destructively reordered in the same manner as for
@Funref[nreverse].  Thus if the argument should not be destroyed, the
user must sort a copy of the argument.

Should execution of the @Kwd[key] function or the @i[predicate] cause an error,
the state of the list or array being sorted is
undefined.  However, if the error is corrected, the sort will, of
course, proceed correctly. 

Note that since sorting requires many comparisons, and thus
many calls to the @i[predicate], sorting will be much faster if the
@i[predicate] is a compiled function rather than interpreted. 
For example:
@lisp
(setq foovector (sort foovector #'string-lessp @Kwd[key] #'car))
@Endlisp
If @f[foovector] contained these items before the sort
@Lisp
("Tokens" "The Lion Sleeps Tonight")
("Carpenters" "Close to You")
("Rolling Stones" "Brown Sugar")
("Beach Boys" "I Get Around")
("Mozart" "Eine Kleine Nachtmusik" (K 525))
("Beatles" "I Want to Hold Your Hand")
@Endlisp
then after the sort @f[foovector] would contain
@Lisp
("Beach Boys" "I Get Around")
("Beatles" "I Want to Hold Your Hand")
("Carpenters" "Close to You")
("Mozart" "Eine Kleine Nachtmusik" (K 525))
("Rolling Stones" "Brown Sugar")
("Tokens" "The Lion Sleeps Tonight")
@Endlisp
@Enddefun

@Defun[Fun {merge⎇, Args {@i[result-type] @i[sequence1] @i[sequence2] @i[predicate]⎇, Keys {[key]⎇]
@Index2[P {merging⎇, S {sorted sequences⎇]
The sequences @i[sequence1] and @i[sequence2] are destructively
merged according to an order determined by
the @i[predicate].  The result is a sequence of type @i[result-type],
which must be a subtype of @f[sequence], as for the function @Funref[coerce].
The @i[predicate] should take two
arguments and return non-@false if and only if the first argument is
strictly less than the second (in some appropriate sense). 
If the first argument is greater than or equal to the second
(in the appropriate sense), then the @i[predicate] should return @false.

The @f[merge] function determines the relationship between two elements
by giving keys extracted from the elements to the @i[predicate].
The @Kwd[key] function, when applied to an element, should return
the key for that element; the @Kwd[key] function defaults to the identity
function, thereby making the element itself be the key.

The @Kwd[key] function should not have any side effects.
A useful example of a @Kwd[key] function would be a component
selector function for a @Macref[defstruct] structure, used to merge
a sequence of structures.

If the @Kwd[key] and @i[predicate] functions always return, then the
merging operation will always terminate.
The result of merging two sequences @i[x] and @i[y] is a new sequence
@i[z], such that the length of @i[z] is the sum of the lengths of @i[x]
and @i[y], and @i[z] contains the all the elements of @i[x] and @i[y].
If @i[x1] and @i[x2] are two elements of @i[x], and @i[x1] precedes
@i[x2] in @i[x], then @i[x1] precedes @i[x2] in @i[z], and similarly for
elements of @i[y].  In short, @i[z] is an @i[interleaving] of @i[x]
and @i[y].

Moreover, if @i[x] and @i[y] were correctly sorted according to the
@i[predicate], then @i[z] will also be correctly sorted.
For example:
@lisp
(merge 'list '(1 3 4 6 7) '(2 5 8) #'<) @EV (1 2 3 4 5 6 7 8)
@Endlisp
If @i[x] or @i[y] is not so sorted, then @i[z] will not be sorted,
but will nevertheless be an interleaving of @i[x] and @i[y].

The merging operation is guaranteed
@i[stable]; if two or more elements are considered equal by the
@i[predicate], then the elements from @i[sequence1] will
precede those from @i[sequence2] in the result.
(The @i[predicate] is assumed to
consider two elements @i[x] and @i[y] to be equal if
@f[(funcall @i[predicate] @i[x] @i[y])] and
@f[(funcall @i[predicate] @i[y] @i[x])] are both false.)
For example:
@lisp
(merge 'string "BOY" "nosy" #'char-lessp) @EV "BnOosYy"
@Endlisp
The result can @i[not] be @f["BnoOsYy"], @f["BnOosyY"], or @f["BnoOsyY"].
The function @Funref[char-lessp] ignores case, and so considers
the characters @f[Y] and @f[y] to be equal, for example;
the stability property then guarantees that the character from the
first argument (@f[Y]) must precede the one from the second
argument (@f[y]).
@Enddefun